package lc_剑指_Offer_II_107_矩阵中的距离;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {

	int[][] direction = new int[][] { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };
	public int[][] updateMatrix(int[][] mat) {
		int m = mat.length, n = mat[0].length;
		int[][] ans = new int[m][n];
		for (int i = 0; i < m; i++) {
			Arrays.fill(ans[i], -1);
		}
		Queue<int[]> queue = new LinkedList<>();
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				int cur = mat[i][j];
				if (cur == 0) {
					ans[i][j] = 0;
					queue.add(new int[] { 0, i, j });
				}
			}
		}
		while (!queue.isEmpty()) {
			int[] q = queue.poll();
			int d = q[0], x = q[1], y = q[2];
			for (int[] nd : direction) {
				int nextx = x + nd[0], nexty = y + nd[1];
				if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n && ans[nextx][nexty] == -1) {
					ans[nextx][nexty] = d + 1;
					queue.add(new int[] { d + 1, nextx, nexty });
				}
			}
		}
		return ans;
	}
}